/**
 * 
 */
package leetCode;

import java.util.Arrays;

/**
 * @author zhong
 *
 */
public class RabbitsinForest {
	public int numRabbits(int[] answers) {
		if (answers == null || answers.length == 0) {
			return 0;
		}
		Arrays.sort(answers);
		int n = answers.length;
		int sum = 0;
		int i = n - 1;
		while (i >= 0 && answers[i] != 0) {
			int count = answers[i] + 1;// 多少只颜色相同的
			sum += count;
			int k = count - 1;// 剩余可以说话的兔子数
			i--;
			while (i >= 0 && (k - (count - answers[i])) >= 0 && answers[i] != 0) {
				k -= (count - answers[i--]);
			}
		}
		if (i != -1) {
			sum += (i + 1);// 前面的都是0，也就是这种兔子单独一种颜色，所以
		}
		return sum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] ans = { 10, 10, 10 };// 1, 1, 2
		System.out.println(new RabbitsinForest().numRabbits(ans));
	}

}
